package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

/**
 * 牛客题霸-研发最爱考
 *
 * 二叉树中是否存在节点和为指定值的路径
 *  算法知识视频讲解
 * 简单  通过率：36.15%  时间限制：1秒  空间限制：64M
 * 知识点
 * 树
 * dfs
 * 题目
 * 题解(8)
 * 讨论(121)
 * 排行
 * 描述
 * 给定一个二叉树和一个值\ sum sum，判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径，
 * 例如：
 * 给出如下的二叉树，\ sum=22 sum=22，
 *
 * 返回true，因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22
 * 示例1
 * 输入：
 * {1,2},0
 * 复制
 * 返回值：
 * false
 * 复制
 * 示例2
 * 输入：
 * {1,2},3
 * 复制
 * 返回值：
 * true
 * 复制
 * 关联企业
 * 关联职位
 */
public class HasPathSum {

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(7);

        System.out.println(hasPathSum(root,8));

    }

    public boolean hasPathSum(TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return false;
        }

        return dfs(root, sum, 0);
    }

    private boolean dfs(TreeNode node, int sum, int temp) {

        temp += node.val;

        if (node.left == null && node.right == null) {
            if (temp == sum) {
                return true;
            } else {
                return false;
            }
        }

        return (node.left != null ? dfs(node.left, sum, temp) : false) || (node.right != null ? dfs(node.right, sum, temp) : false);
    }

}
